import java.util.HashSet;
import java.util.Set;

/**
 * @Description: 环形链表 II
 * https://leetcode.cn/problems/linked-list-cycle-ii/
 * @Date:Create in 20:10  2022/6/30
 */
public class detectCycle0142 {


    //哈希表
    public ListNode detectCycle1(ListNode head) {
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode cur = head;

        while (cur != null) {

            if(!set.contains(cur)){
                set.add(cur);
                cur = cur.next;
            }else{
                return cur;
            }

        }
        return null;
    }

    //快慢指针 数学问题
    public ListNode detectCycle2(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast !=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}
